package com.fps.webshop.question.question0200_0299;

/**
 * 278. 第一个错误的版本
 * 
 * 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
 * 
 * 假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
 * 
 * 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
 * 
 * 示例 1：
 * 输入：n = 5, bad = 4
 * 输出：4
 * 解释：
 * 		调用 isBadVersion(3) -> false 
 * 		调用 isBadVersion(5) -> true 
 * 		调用 isBadVersion(4) -> true
 * 		所以，4 是第一个错误的版本。
 * 
 * 示例 2：
 * 输入：n = 1, bad = 1
 * 输出：1
 * 
 * 提示：
 * 		1 <= bad <= n <= 231 - 1
 */
public class Question278 {
	
	static int bad  = 0;
	
	
	static boolean isBadVersion(int version){
		if(version>=bad) {
			return true;
		}else {
			return false;
		}
	}
	
	
	
	
	/**
	 * 第一次提交，二分查找的变形，但时间还是不太理想
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		12 ms	35.2 MB	Java	2021/08/09 17:04
	 */
	public static int firstBadVersion1(int n) {
        int start = 0;
        while(start<=n) {
        	int mildle = start + (n-start)/2;
        	if(isBadVersion(mildle)) {
        		n = mildle-1;
        	}else {
        		start = mildle+1;
        	}
        }
        if(isBadVersion(start)) {
        	return start;
        }else {
        	return -1;
        }
    }
	
	/**
	 * 第二次提交，二分查找的变形，相信题目条件，去掉最后一次isBadVersion的判断
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		11 ms	35.1 MB	Java	2021/08/09 17:06
	 */
	public int firstBadVersion2(int n) {
        int start = 0;
        while(start<=n) {
        	int mildle = start + (n-start)/2;
        	if(isBadVersion(mildle)) {
        		n = mildle-1;
        	}else {
        		start = mildle+1;
        	}
        }
        return start;
    }
	
	public static void main(String[] args) {
		bad = 3;
		System.out.print(firstBadVersion1(8));
	}
}
